package pri.zjy.tree;

import pri.zjy.tree.model.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangjy
 * @description 二叉树的最小深度
 * <p>
 * 给定一个二叉树，找出其最小深度。
 * <p>
 * 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
 * <p>
 * 说明：叶子节点是指没有子节点的节点。
 * @date 2025/4/8 10:55
 */
public class MinDepth_111 {

    /**
     * 个解：递归-先序
     * <p>
     * 从0开始统计层数
     */
    int ans6 = Integer.MAX_VALUE;

    public int minDepth6(TreeNode root) {
        if (root == null) return 0;

        dfs6(root, 0);
        return ans6;
    }

    public void dfs6(TreeNode node, int depth) {
        if (node == null) return;

        // 根
        // 记录本层的层级
        depth++;
        // 只有到叶子节点，才记录最小深度
        if (node.left == null && node.right == null) {
            ans6 = Math.min(ans6, depth);
        }

        // 左
        dfs6(node.left, depth);
        // 右
        dfs6(node.right, depth);
    }

    /**
     * dmsxl解法：dfs-递归-后序.
     * <p>
     * 分析：
     * <p>
     * 由题可知，最小深度是根节点root 到叶子节点，所以，如果root左、右只有一个空的情况，空的子树不没有叶子节点，不应该记录为最小深度。
     * 如果题目没有说到叶子节点，那么root左空、右不空的情况，最小深度为1，最后代码实现和二叉树最大深度基本相同。
     * <p>
     * 二叉树的最小深度，可以转化为，二叉树的最小高度（如下面，递归-后序的实现）。
     */
    public int minDepth5(TreeNode root) {
        if (root == null) return 0;

        int minLeft = minDepth5(root.left);
        int minRight = minDepth5(root.right);

        // 中
        int minChild = 0;
        if (root.left != null && root.right == null) {
            // 左非空，右空
            minChild = minLeft;
        } else if (root.left == null && root.right != null) {
            // 左空，右非空
            minChild = minRight;
        } else {
            // 左、右都非空
            minChild = Math.min(minLeft, minRight);
        }
        return minChild + 1;
    }

    /**
     * 个解：dfs-递归-后序；
     * 这里实现的后序并不明朗；可以参考dmsxl解法，是较为明显的后序。
     */
    public int minDepth4(TreeNode root) {
        if (root == null) return 0;
        // 叶子节点才记录高度
        if (root.left == null && root.right == null) return 1;

        int minChild = 0;
        if (root.left != null && root.right == null) {
            // 左非空，右空
            minChild = minDepth4(root.left);
        } else if (root.left == null) {
            // 左空，右非空
            minChild = minDepth4(root.right);
        } else {
            // 左、右都非空
            minChild = Math.min(minDepth4(root.left), minDepth4(root.right));
        }

        // 中
        return minChild + 1;
    }

    /**
     * 个解-dfs-递归-前序；
     * 只有到叶子节点，才记录最小深度。
     */
    int ans = Integer.MAX_VALUE;

    public int minDepth3(TreeNode root) {
        if (root == null) return 0;

        dfs3(root, 1);
        return ans;
    }

    public void dfs3(TreeNode node, int depth) {
        if (node == null) return;

        // 根
        // 只有到叶子节点，才记录最小深度
        if (node.left == null && node.right == null) {
            ans = Math.min(ans, depth);
        }
        depth++;
        // 左
        dfs3(node.left, depth);
        // 右
        dfs3(node.right, depth);
    }

    /**
     * 个解-BFS；
     * 最小深度 = 层数（假设层数从1开始）
     */
    public int minDepth2(TreeNode root) {
        if (root == null) return 0;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        // 表示层数
        int minDepth = 0;
        while (!queue.isEmpty()) {
            int curLayerSize = queue.size();
            minDepth++; // 记录最小层数，即最小深度
            for (int i = 0; i < curLayerSize; i++) {
                TreeNode poll = queue.poll();
                // 本层任一节点的左右孩子都为空，表示该节点为叶子节点，所以找到最小深度
                if (poll.left == null && poll.right == null) return minDepth;

                if (poll.left != null) queue.offer(poll.left);
                if (poll.right != null) queue.offer(poll.right);
            }
        }
        return minDepth;
    }

    /**
     * dfs（参考官解）；
     * 注意：
     * 只有当左右孩子都为空的时候，才说明是遍历的最低点。如果其中一个孩子为空则不是最低点。如：根节点只有左没右孩子，那其最小深度就只用看右孩子，其左没有叶子节点，不用考虑左
     */
    public int minDepth(TreeNode root) {
        if (root == null) return 0;
        if (root.left == null && root.right == null) {
            return 1;
        }

        int minDepth = Integer.MAX_VALUE;
        if (root.left != null) {
            int minLeft = minDepth(root.left);
            minDepth = Math.min(minLeft, minDepth);
        }
        if (root.right != null) {
            int minRight = minDepth(root.right);
            minDepth = Math.min(minRight, minDepth);
        }

        // 本层的最小深度
        return minDepth + 1;
    }

}
